#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<cstring>
using namespace std;
class Solution {
    int as[31];
public:
    int fib(int n) {
        memset(as, -1, sizeof(as));
        return dfs(n);
    }
    int dfs(int i)
    {
        if (as[i] != -1)
        {
            return as[i];
        }
        if (i == 0)
        {
            return 0;
        }
        if (i == 1 || i == 2)
        {
            return 1;
        }
        as[i] = dfs(i - 1) + dfs(i - 2);
        return as[i];
    }
};